package com.leetcode.dynamic_programming.bag;

import java.util.Scanner;

/**
 * @author Dennis Li
 * @date 2020/10/13 21:56
 */
public class ZeroOneBag {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt(), v = scanner.nextInt();
        int[][] items = new int[n][2];
        int[] dp = new int[v + 1];

        for (int i = 0; i < n; i++) {
            items[i][0] = scanner.nextInt();
            items[i][1] = scanner.nextInt();
        }
        for (int i = 1; i <= n; i++) {
            int[] item = items[i];
            for (int j = v; j >= item[0]; j--) {
                // 遍历的方向始终要保证所需状态是已经计算出来的
                // 对于这里一轮的遍历来说 -- j - item[0] 暂时没有被计算过
                // 要用上一轮的结果的话，并且大小是在递减，那么就考虑从后向前进行遍历
                dp[j] = Math.max(dp[j], dp[j - item[0]] + item[1]);
            }
        }
        System.out.println(dp[v]);
    }

}
